1. Field of the Invention
This invention relates to Extensible Markup Language Path Language (XPath) Expressions and more particularly relates to optimization of XPath expressions in a database management system configured to accept Extensible Markup Language (XML) queries.
2. Description of the Related Art
XPath and XQuery are two common languages used to query for XML data from an XML document or from a database management system. XPath is a path expression language for selecting data within XML documents. XQuery is a language for querying, transforming, and constructing XML data. An expression is a string of unicode characters which may be constructed from keywords, symbols, and operands. XPath allows expressions to be nested. XQuery uses XPath expression syntax to address specific parts of an XML document and is semantically similar to structured query language (SQL). The SQL-like XQuery syntax uses “For,” “Like,” “Where,” “Order by,” and “Return” clauses in a “FLWOR” expression.
XPath engines typically analyze an XML document as an XML tree by representing each element of the XML document as a node in the XML tree. The XML tree may include parent-child nodes that directly correspond to the nested elements in the XML document. For more information regarding XPath and XQuery please visit the proposed recommendations of W3C which currently reside at http://www.w3.org/TR/xpath20/and http://www.w3.org/TR/xquery/ respectively.
Several XML Database Management Systems (DBMS) support XQuery and/or SQL/XML languages, which are based on navigational primitives in the form of XPath expressions. Typically, these systems either model each XPath step as a separate query plan operator, or employ holistic approaches that can evaluate multiple steps of a single XPath expression. Furthermore, some proposals recommend executing as many XPath expressions as possible within a single FLWOR block simultaneously in a data streaming context.
However, combining all possible XPath expressions for concurrent execution can result in significant performance degradation for two reasons. First, grouping all XPath expressions on a single document does not always work if the query involves more than one data source or has nested query blocks. Second, merging XPath expressions may result in unnecessary execution of branches that would be filtered by predicates in other branches or elsewhere in the query.